﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Engine.Sgml.Allocation {
    internal sealed class TreeNodeIterator {
        private int originDepth;
        private int index;
        private TreeNodeLocation nodeLocation;
        private List<TreeNodeItem> chain = new List<TreeNodeItem>();

        public void Reset(SElement ancestor, ref TreeNodeItem previous, ref TreeNodeItem next) {
            Debug.Assert(previous.Location != TreeNodeLocation.Ancestor);
            Debug.Assert(next.Location != TreeNodeLocation.Ancestor);

            index = -1;
            chain.Clear();
            nodeLocation = previous.Location;

            if (previous.Element != null) {
                chain.Add(previous);
                originDepth = previous.Element.Depth;
                }
            if (next.Element != null) {
                chain.Add(next);
                originDepth = next.Element.Depth;
                }
            if (ancestor != null) {
                chain.Add(new TreeNodeItem {
                    Element = ancestor,
                    Location = TreeNodeLocation.Ancestor
                });
                originDepth = ancestor.Depth + 1;
                }
            }

        public bool MoveNext() {
            if (chain.Count == 0)
                return false;
            if (++index < chain.Count)
                return true;
            for (int i = 0; i < chain.Count; i++) {
                TreeNodeItem item = chain[i];
                switch (item.Location) {
                    case TreeNodeLocation.None:
                        Debug.Assert(false, "The tree node iterator is moved to the 'None' item.");
                        throw new InvalidOperationException();
                    case TreeNodeLocation.Ancestor:
                        SElement element = null;
                        if (nodeLocation == TreeNodeLocation.Previous) {
                            element = item.Element.PreviousNonInclusionNode();
                            if (element != null)
                                chain.Insert(i++, new TreeNodeItem { Element = element, Location = TreeNodeLocation.Previous });
                            element = item.Element.NextNonInclusionNode();
                            if (element != null)
                                chain.Insert(i++, new TreeNodeItem { Element = element, Location = TreeNodeLocation.Next });
                            }
                        else {
                            element = item.Element.NextNonInclusionNode();
                            if (element != null)
                                chain.Insert(i++, new TreeNodeItem { Element = element, Location = TreeNodeLocation.Next });
                            element = item.Element.PreviousNonInclusionNode();
                            if (element != null)
                                chain.Insert(i++, new TreeNodeItem { Element = element, Location = TreeNodeLocation.Previous });
                            }
                        element = item.Element.Parent;
                        if (element == null)
                            chain.RemoveAt(i);
                        else
                            chain[i] = new TreeNodeItem { Element = element, Location = TreeNodeLocation.Ancestor };
                        break;
                    case TreeNodeLocation.Previous:
                        element = item.Element.PreviousNonInclusionNode();
                        if (element == null) {
                            element = item.Element.LastNonInclusionNode();
                            if (element == null)
                                chain.RemoveAt(i--);
                            else
                                chain[i] = new TreeNodeItem { Element = element, Location = TreeNodeLocation.Previous };
                            }
                        else {
                            chain[i] = new TreeNodeItem { Element = element, Location = TreeNodeLocation.Previous };
                            element = item.Element.LastNonInclusionNode();
                            if (element != null)
                                chain.Insert(++i, new TreeNodeItem { Element = element, Location = TreeNodeLocation.Previous });
                            }
                        break;
                    case TreeNodeLocation.Next:
                        element = item.Element.NextNonInclusionNode();
                        if (element == null) {
                            element = item.Element.FirstNonInclusionNode();
                            if (element == null)
                                chain.RemoveAt(i--);
                            else
                                chain[i] = new TreeNodeItem { Element = element, Location = TreeNodeLocation.Next };
                            }
                        else {
                            chain[i] = new TreeNodeItem { Element = element, Location = TreeNodeLocation.Next };
                            element = item.Element.FirstNonInclusionNode();
                            if (element != null)
                                chain.Insert(++i, new TreeNodeItem { Element = element, Location = TreeNodeLocation.Next });
                            }
                        break;
                    default:
                        break;
                    }
                }
            if (chain.Count > 0) {
                SortChain();
                index = 0;
                return true;
                }
            else
                return false;
            }

        private void SortChain() {
            if (chain.Count < 2)
                return;
            int q = 0;
            int b = 1;
            index = 0;
            int d = originDepth;
            do {
                for (int i = index; i < chain.Count; i++) {
                    if (chain[i].Element.Depth == d)
                        index++;
                    else
                        break;
                    }
                for (int i = index; i < chain.Count; i++) {
                    if (chain[i].Element.Depth == d) {
                        TreeNodeItem item = chain[i];
                        chain.RemoveAt(i);
                        chain.Insert(index++, item);
                        }
                    }
                d += (++q * b);
                b = -b;
                } while (index < chain.Count);
            }

        public TreeNodeItem Current {
            get {
                if (0 <= index && index < chain.Count)
                    return chain[index];
                else
                    return default(TreeNodeItem);
                }
            }
        }
    }
